#include <stdio.h>
#include <stdlib.h>
#include "List.h"

ListPtr createList()
{
    ListPtr list;
    list = (ListPtr) malloc(sizeof(List));
    list->size = 0;
    list->head = NULL;
    list->tail = NULL;
    return list;
}

void freeList(const ListPtr L)
{
    //Not exactly sure how to do this since I don't know much about freeing memory manually in a program yet.
    //I assume that we have to first free every node in the list, THEN free the actual list, so I will loop through
    //each node in the list and free it, then free the list
    
        
    //Next, we'll take care of a list with no nodes
    if(L->head == NULL && L->tail == NULL){
       free(L);
       return;
    }
  
    //Now we'll take care of a list that has nodes in it
    
    NodePtr temp = L->head; //Create a temporary node pointer variable and set it to the head node
    NodePtr nextNode; //Create another temp variable to hold the pointer to the next node since we will be deleting nodes and won't be able to access it directly
    
    //Loop through the list and free every node
    while(temp != NULL){
	nextNode = temp->next;
        freeNode(temp);
	temp = nextNode;
    }
    
    //Now free the list
    free(L);
   
    
    return;  
    
}

int getSize(const ListPtr L)
{
  if(L == NULL){
      return 0; //Return 0 if pointer is NULL
  }
  
  //Am going to do this the easy way and just return the list's size variable! =P  
  
  return L->size;
}

Boolean isEmpty(const ListPtr L)
{
  //I am writing this function assuming that an empty list will consist of one of the following 2 scenarios:
  //FIRST: The list exists, but both the head and tail pointers are NULL
  //OR
  //SECOND: The pointer passed to this function is NULL, in which case we will return that the list is empty
  
  //Handle the first scenario
  if(L->head == NULL && L->tail == NULL){ //For this to work right, your tail pointer must be set correctly in all your other functions!! (and your head too of course)
      return 1; //Return TRUE (or 1)
  }
  
  //Handle the second scenario
  if(L == NULL){
      return 1; //Return TRUE
  }
  
  return 0; //Return FALSE otherwise which says the list ISN'T empty
}

void addAtFront(ListPtr list, NodePtr node)
{
	//I actually got this code from the "generic-with-library" folder.
	//I figured since it was already there, why try to figure it out!
	//That's one of the first rules of coding, don't re-invent the wheel.
	//Meaning if the code already exists, why waste time creating it again?
	//Anyway, I copied the code over here and added comments on everything
	//to help explain what everything does, since I do understand it all.
	//You don't want to just copy code and not understand what it does
	//or you will never learn that way! :)
  
	//Make sure that both the list and node passed actually exist. If not, exit.
	if (list == NULL) return;
	if (node == NULL) return;
	
	//NEW CODE 10/16/14
	//I forgot to test to make sure the node isn't already in the list before attempting to add it.
	//First, I will loop through the list and make sure the node isn't in there.
	
	NodePtr temp = list->head; //Create temporary node pointer for looping
	
	
	//Loop through the list and see if the node "next" is pointing to is
	//the node we are supposed to remove. If no "next" pointer points to that node,
	//then we know it's not in the list.
	  
	  //Only loop through the list is there's at least 1 node in the list
	  if(list->size > 0){
	    
	    //First check if the head node is the node we are trying to add, if it is, we don't have to loop
	    if(list->head == node){
	       return; 
	    }
	    
	    while(temp->next != NULL){
		if(temp->next == node){
		  //If the node is already in the list, exit the function before any operations are performed
		  return;
		}
		temp = temp->next;
	    }
	  }
	
	//END OF NEW CODE
	
	
	
	list->size++; //Increments the list's size counter since we are adding a node to it
	
	//Make the next pointer of the node we are adding point to the node that was
	//in the head position since we are pushing that one to the 2nd position
	node->next = list->head;  
	
	node->prev = NULL; //Set the prev pointer of the node we are adding to NULL since it will be in the head position
	
	if (list->head == NULL) { //If this is the first node added to the list, then both head and tail will point to this same node
		list->head = node;
		list->tail = node;
	}
	else { //This isn't the first node added to the list
	    list->head->prev = node; //Set the prev pointer on the node that USED to be the head to the node we are adding
	    list->head = node;  //Set the head node of the list to be the node we are adding since it's now at the front of the list
	}
}

void addAtRear(ListPtr list, NodePtr node)
{
   //Make sure that both the list and node passed actually exist. If not, exit.
   if (list == NULL) return;
   if (node == NULL) return;
   
	//NEW CODE 10/16/14
	//I forgot to test to make sure the node isn't already in the list before attempting to add it.
	//First, I will loop through the list and make sure the node isn't in there.
	
	NodePtr temp = list->head; //Create temporary node pointer for looping
	
	
	//Loop through the list and see if the node "next" is pointing to is
	//the node we are supposed to remove. If no "next" pointer points to that node,
	//then we know it's not in the list.
	  
	  //Only loop through the list is there's at least 1 node in the list
	  if(list->size > 0){
	    
	    //First check if the head node is the node we are trying to add, if it is, we don't have to loop
	    if(list->head == node){
	       return; 
	    }
	    
	    while(temp->next != NULL){
		if(temp->next == node){
		  //If the node is already in the list, exit the function before any operations are performed
		  return;
		}
		temp = temp->next;
	    }
	  }
	
	//END OF NEW CODE
   
   
   
   list->size++; //Increments the list's size counter since we are adding a node to it
   
   node->prev = list->tail; //The previous node to the one we are adding will be the old tail node since we're adding it on the end.
   
   node->next = NULL; //Since it will be the last node on the end, the "next" pointer will be NULL
   
   if (list->head == NULL) { //If this is the first node added to the list, then both head and tail will point to this same node
	list->head = node;
	list->tail = node;
   }
     else { //This isn't the first node added to the list
	list->tail->next = node; //Set the next pointer on the node that USED to be the tail to the node we are adding
	list->tail = node;  //Set the tail node of the list to be the node we are adding since it's now at the end of the list
     }
}

NodePtr removeFront(ListPtr list)
{
  //Make sure that the list passed actually exists. If not, exit.
   if (list == NULL) return NULL;
   
   //Make sure there is at least 1 node in the list, or return NULL
   if(list->size < 1){
      return NULL;
   }
   
   //If there is only 1 node in the list, then we can just free the head node and set head and tail to NULL
   if(list->size == 1){
      freeNode(list->head); //Free the node
      list->head = NULL; //Set head to NULL since no nodes exist in the list
      list->tail = NULL; //Set tail to NULL since no nodes exist in the list
      list->size--; //Decrease the list size by 1
      return list->head; //Returning a pointer to the new head node for now since I'm not sure what NodePtr this function is supposed to return??
   }
   
   //If there are more than 1 nodes in the list, then we can just set the second node to the head node and free the 1st node
   NodePtr temp; //Create a variable to temporary hold the pointer to the second node
   
   temp = list->head->next; //Holds the pointer to the second node, which is soon to be the head node
   freeNode(list->head); //Free the current head node
   list->head = temp; //Set the second node to the head node
   list->head->prev = NULL; //Set the prev pointer of the new head node to NULL since it's the head node
   list->size--; //Decrease the list size by 1
   return list->head; //Returning a pointer to the new head node for now since I'm not sure what NodePtr this function is supposed to return??
}

NodePtr removeRear(ListPtr list)
{
   //Make sure that the list passed actually exists. If not, exit.
   if (list == NULL) return NULL;
   
   //Make sure there is at least 1 node in the list, or return NULL
   if(list->size < 1){
      return NULL;
   }
   
   //If there is only 1 node in the list, then we can just free the tail node and set head and tail to NULL
   if(list->size == 1){
      freeNode(list->tail); //Free the node
      list->head = NULL; //Set head to NULL since no nodes exist in the list
      list->tail = NULL; //Set tail to NULL since no nodes exist in the list
      list->size--; //Decrease the list size by 1
      return list->head; //Returning a pointer to the head node for now since I'm not sure what NodePtr this function is supposed to return??
   }
   
   //If there are more than 1 nodes in the list, then we can just set the second node to the head node and free the 1st node
   NodePtr temp; //Create a variable to temporary hold the pointer to the second node
   
   temp = list->tail->prev; //Holds the pointer to the second-to-last node, which is soon to be the tail node
   freeNode(list->tail); //Free the current tail node
   list->tail = temp; //Set the second-to-last node to the tail node
   list->tail->next = NULL; //Set the next pointer of the new tail node to NULL since it's the tail node
   list->size--; //Decrease the list size by 1
   return list->head; //Returning a pointer to the head node for now since I'm not sure what NodePtr this function is supposed to return??
}

NodePtr removeNode(ListPtr list, NodePtr node)
{
  //Make sure that both the list and node passed actually exist. If not, exit.
   if (list == NULL) return NULL;
   if (node == NULL) return NULL;
  
  //This shouldn't be too hard since we are already passed the pointer to the node we have
  //to remove. So we don't have to find it ourselves!
  
  //First handle if the node we need to remove is the head or tail node
  if(list->head == node){
     removeFront(list);
     return list->head; //Returning a pointer to the head node for now since I'm not sure what NodePtr this function is supposed to return??
  }
  if(list->tail == node){
      removeRear(list);
      return list->head; //Returning a pointer to the head node for now since I'm not sure what NodePtr this function is supposed to return??
  }
  
  //That was easy! Now, handle removing a node from the middle of the list somewhere.
  
  //If the node is in the middle of the list somewhere, then theoretically all we have to do is
  //make the next pointer of the node before it point to the node after it. And make the prev
  //pointer of the node after it point to the node in front of it. Then free the node.
  //Since it's in the middle of the list, we don't have to mess with heads or tails.
  
  //NEW CODE 10/14/14
  //I forgot to test to make sure the node is in the list before attempting to remove it.
  //First, I will loop through the list and make sure the node is in there, before removing it.
  
  NodePtr temp = list->head; //Create temporary node pointer for looping
  short int exists = 0; //Create a variable to hold if the node exists in the list. 0 if it doesn't, 1 if it does;
  
  //Loop through the list and see if the node "next" is pointing to is
  //the node we are supposed to remove. If no "next" pointer points to that node,
  //then we know it's not in the list.
    while(temp->next != NULL){
	if(temp->next == node){
	  exists = 1;
	}
	temp = temp->next;
    }
  
  //END OF NEW CODE
  
  //Only remove node if it is in the list
  if(exists == 1){
    node->prev->next = node->next;
    node->next->prev = node->prev;
    freeNode(node);
    list->size--; //Decrease list size by 1
  }
  
  return list->head; //Returning a pointer to the head node for now since I'm not sure what NodePtr this function is supposed to return??
}

NodePtr search(const ListPtr list, const int key)
{
  //Not sure what this function is supposed to do??
  //Am skipping it for now.
  //Not sure what we are supposed to search in the list when we are passed an integer??
  //The only thing I can think of is maybe a Job ID?? Not sure?
  
  return NULL;
}

void reverseList(ListPtr L)
{
  //Make sure that the list passed actually exists. If not, exit.
   if (L == NULL) return;
  
  NodePtr head = L->head; //Create a NodePtr to the head node of the list
  NodePtr t; //Create a variable to use as a temporary holder in the loop
  
    //The following loop reverses the list by swapping the previous and next pointers
    //in each node. The nodes themselves don't actually move in memory.
    
    while(1)
    {
       t = head->prev; //Store the current prev pointer in a temporary variable
       head->prev = head->next; //Sets prev to next
       head->next = t; //Effectively sets next to prev since we stored prev into t above
       
       //Ok, now next and prev are swapped in the current node.
       //Now we advance our Node Pointer (head) to the next node in the list
 
       if(head->prev != NULL){ //If this isn't the last node in the original list
          head = head->prev; //Set our Node Pointer to the next node in the original list
          
          //The reason that says "prev" instead of "next" is that we swapped next and prev so the pointer to the next
          //node in the original list is actually saved in "prev" now.
       }
       else{ 
	 break;
       }
    }
    //Now that we have all the next and prev pointers swapped, all we have to do is
    //change the actual pointer that points to the "head" and "tail" nodes of the list. We change
    //the head pointer to point to the node that was actually last in the original list. But first
    //we set the tail to the node that used to be the head since the list is reversed.
    L->tail = L->head;
    L->head = head;
}

void printList(const ListPtr L)
{
    NodePtr temp = L->head; //Create a temporary variable holding the address of the head node of the list
    int i;
    
    //Add blank line before output
    printf("\n");
    
    //Now print the list from head to tail
    for(i = 1; i <= L->size; i++){
	printf("%s (next=%p) (prev=%p)\n",toString(temp->data), temp->next, temp->prev); //Prints the data out by calling the toString function (which is found in Job.c)
	temp = temp->next; //Advance the pointer to point to the next node
    }
    
    //Add blank line after output
    printf("\n");
    
}
